{% extends "pages/base.html" %} {% block title %}Home{% endblock %} {% block content %}
Câu 4143447 Loại câu: minmax

Số phép so sánh tối thiểu cần sử dụng để tìm ra cả giá trị lớn nhất lẫn giá trị nhỏ nhất của một dãy gồm {N} phần tử là bao nhiêu?

Ghi ra một số nguyên duy nhất là kết quả đáp án.

-----------------------------------------------------------

Gợi ý phương pháp: Chia dãy thành hai nửa, tìm min và max mỗi nửa rồi so sánh chúng với nhau để tổng hợp kết quả. 

Xét mảng arr[lo..hi], mã giả để tìm min và max của mảng này như sau:

Algorithm: minmax(lo, hi)

if hi – lo ≤ 1 then  
   return (max(arr[lo], arr[hi]), min((arr[lo], arr[hi])) 
else 
   (max1, min1):= minmax(lo, ⌊((lo + hi)/2)⌋) 
   (max2, min2):= minmax(⌊((lo + hi)/2) + 1)⌋, hi) 
return (max(max1, max2), min(min1, min2))

Đáp án [100]

3*{N}/2-2
Câu 4143448 Loại câu: Chia để trị (Dễ) - Cây tìm kiếm nhị phân
Trong một cây tìm kiếm nhị phân T bao gồm n nút khác nhau. Độ phức tạp thời gian của thủ tục lấy một phần tử trong T mà không phải là phần tử lớn nhất trong T là bao nhiêu?

Đáp án [100] O(1)


[0] O(n)


[0] O(nlogn)


[0] O(logn)


[0] Không đáp án nào đúng
Câu 4143449 Loại câu: Chia để trị (Dễ) - Loại thuật toán

Trong các thuật toán dưới đây, thuật toán nào không phải là thuật toán chia để trị?

Đáp án [50]


Sắp xếp vun đống

[0] Sắp xếp nhanh


[0] Sắp xếp trộn


[0] Tìm kiếm nhị phân


Đáp án [50]


Sắp xếp chèn

Câu 4143450 Loại câu: Chia để trị (Dễ) - Tính hàm mũ
Bạn được yêu cầu viết lại hàm pow(x, n) có chức năng tính xn (n là số tự nhiên). Độ phức tạp tính toán tốt nhất có thể của hàm này là bao nhiêu?

Đáp án [100] O(logn)


[0] O(n)


[0] O(nlogn)


[0] O(1)


[0] O(log(logn))


[0] Không đáp án nào đúng
Câu 4143451 Loại câu: Chia để trị (Trung bình) - Độ phức tạp

Điều nào sau đây là đúng về độ phức tạp thuật toán là nghiệm của hệ thức truy hồi T(n)=2T(n/2) + logn với T (1) = 1?


Đáp án [100] O(n)


[0] O(nlogn)


[0] O(logn)


[0] O(n2)


[0] Không đáp án nào đúng
Câu 4143452 Loại câu: Chia để trị (Trung bình) - So sánh thuật toán sắp xếp

Cho mảng gồm các phần tử sau, 23, 32, 45, 69, 72, 73, 89, 97. Thuật toán sắp xếp nào dưới đây sử dụng ít phép so sánh nhất để sắp xếp mảng tăng dần?

[0]

Selection sort

Đáp án [100]

Insertion sort

[0] Merge sort


[0] Quick sort sử dụng phần tử cuối cùng là phần tử pivot
Câu 4143453 Loại câu: Chia để trị (Trung bình) - Thuật toán tìm ước số chung lớn nhất

Thuật toán dưới đây có chức năng gì?

Đáp án [100]

Tìm ước số chung lớn nhất của x và y

[0] Tính tổng x+y


[0] Tính phần dư của x chia cho y


[0] Tìm bội số chung nhỏ nhất của x và y


[0] Không đáp án nào đúng
Câu 4143454 Loại câu: Dãy con chung dài nhất - instance 1 (bản sao) (bản sao)

Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.

Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?

[0]

3

Đáp án [100]

4

[0]

5

[0]

6

[0] Đáp án khác
Câu 4143455 Loại câu: Deque

Cấu trúc dữ liệu Deque cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?


[0] vào một đầu, ra đầu còn lại


Đáp án [100] vào và ra được từ cả hai đầu


[0] vào và ra duy nhất một đầu


[0] không cách nào trong các cách ở đây


[0] Đáp án khác
Câu 4143456 Loại câu: Độ phức tạp thuật toán duyệt toàn bộ (copy)

Một thuật toán duyệt toàn bộ được gọi là hiệu quả:

[0] khi có độ phức tạp tính toán là hàm mũ


[0] khi có độ phức tạp tính toán là đa thức


Đáp án [50]


khi có độ phức tạp tính toán là hằng số

[0] khi có độ phức tạp khấu trừ là tuyến tính


Đáp án [50]


khi có độ phức tạp khấu trừ là hằng số

[0] khi có độ phức tạp khấu trừ là đa thức


[0] Không mệnh đề nào trong các mệnh đề ở đây thoả mãn
Câu 4143457 Loại câu: Kỹ năng khóa học (Dễ)

Trong các kỹ năng cơ bản dưới đây, kỹ năng nào cần rèn luyện trong khoá học?

[0] Kỹ năng đọc đề


[0] Kỹ năng phân loại bài toán


[0]

Kỹ năng kiểm thử chương trình



[0] Kỹ năng phân tích thuật toán


Đáp án [100] Tất cả các kỹ năng ở đây
Câu 4143458 Loại câu: master theorem (copy) (copy)

Giả sử độ phức tạp tính toán của giải thuật chia để trị khi giải một bài toán kích thước n có công thức truy hồi như sau:

$$ T(n) = 9 T(n/3) + n^2 $$

Dùng định lý thợ (master theorem), hãy xác định độ phức tạp tính toán của giải thuật trong trường hợp trên.

Đáp án [100]

\(\Theta(n^2logn) \)

[0]

\(\Theta(nlogn) \)

[0]

\(\Theta(n^2) \)

[0]

\(\Theta(nlog^2n) \)

[0] Đáp án khác
Câu 4143459 Loại câu: Mục tiêu khoá học (Dễ)

Trong các mục tiêu dưới đây, đâu là mục tiêu chính của môn học Thuật toán ứng dụng? (Có thể trả lời nhiều đáp án)

Đáp án [25]

Tăng cường khả năng mô hình hoá bài toán thực tế



Đáp án [25]

Tăng cường kỹ năng đề xuất Cấu trúc dữ liệu và Thuật toán cho các bài toán thực tế




Đáp án [25]

Tăng cường kỹ năng chuyển hoá thiết kế Cấu trúc dữ liệu và Thuật toán sang chương trình có thể chạy được và đúng




Đáp án [25]

Tăng cường kỹ năng lập trình ngôn ngữ





[0]

Tăng cường kỹ năng phân tích, thiết kế các hệ thống thông tin lớn
Câu 4143460 Loại câu: Nhỏ nhất thứ k

Giả sử cho trước hàm sau:

   int partition (int a[], int n); 

Hàm này lấy phần tử đầu tiên của mảng a[] làm phần tử chốt, sau đó sắp xếp các phần tử nhỏ hơn hoặc bằng phần từ chốt về  phần bên trái của mảng, và tất cả phần tử lớn hơn phần tử chốt về phần bên phải của mảng. Ngoài ra, hàm cũng di chuyển phần tử chốt về vị trí cuối cùng của phần bên trái. Hàm trả về số lượng phần tử của phần bên trái. 

Đoạn chương trình C bị khuyết sau sử dụng hàm partition function để tìm phần tử nhỏ thứ k trong mảng a[] kích thước n (giả định k ≤ n). Hãy lựa chọn phần danh sách tham số đúng trong các phương án dưới đây để điền vào chỗ trống.

int kth_smallest (int a[], int n, int k) {
   int left_end = partition (a, n);
   if (left_end+1==k){
       return a [left_end];
   }
   if (left_end+1 > k) {
      return kth_smallest (____________________);
   }
   else {
      return kth_smallest (____________________);
    }
}

Đáp án [100]

(a, left_end, k) và (a+left_end+1, n–left_end–1, k–left_end–1)

[0]

(a, left_end, k) và (a, n–left_end–1, k–left_end–1)

[0]

(a, left_end+1, N–left_end–1, K–left_end–1) và (a, left_end, k)

[0]

(a, n–left_end–1, k–left_end–1) và (a, left_end, k)

[0] Đáp án khác
Câu 4143461 Loại câu: Phương pháp cài đặt

Thuật toán chia để trị thường được lập trình theo phương pháp nào sau đây?

Đáp án [100]

Đệ quy

[0]

 Dùng các vòng lặp

[0]

Quay lui

[0]

Dùng cú pháp lambda

[0] Đáp án khác
Câu 4143462 Loại câu: Phương pháp giải (Trung bình) - So sánh thuật toán

Trong những nhận định dưới đây về thuật toán chia để trị và quy hoạch động, nhận định nào đúng? (có thể chọn nhiều đáp án)

Đáp án [33.33333] Chia để trị thường được cài đặt bằng kỹ thuật đệ quy


Đáp án [33.33333] Quy hoạch động có thể được cài đặt bằng vòng lặp


[0] Trong quá trình giải bài toán, cả chia để trị và quy hoạch động đều cho độ phức tạp thuật toán trong thời gian đa thức


Đáp án [33.33333] Chia để trị chia bài toán lớn thành các bài toán con độc lập, trong khi đó quy hoạch động thì chia bài toán lớn thành các bài toán con gối nhau
Câu 4143463 Loại câu: Phương pháp giải 1 (Dễ)

Đại dịch COVID19 diễn ra phức tạp trên toàn thế giới. Việt Nam cũng không phải là ngoại lệ. Rất nhiều người đã bị chết vì dịch bệnh. Công ty phân tích dữ liệu XTEC muốn thống kê số lượng người chết theo các độ tuổi: nhỏ hơn 15, từ 15 tới 20, từ 20 tới 40, từ 40 tới 60 và trên 60. Yêu cầu, cho trước một danh sách người chết vì dịch bệnh và độ tuổi của những người này, hãy đưa ra số lượng người chết theo các độ tuổi trên.

Bài toán này thuộc dạng bài nào trong các dạng bài sau:

Đáp án [100] Adhoc


[0] Chia để trị


[0] Quy hoạch động


[0] Thuật toán đặc thù


[0] Thuật toán trên đồ thị


[0] Đáp án khác
Câu 4143464 Loại câu: Phương pháp giải 2 (Trung bình)

Để giải nhanh và chính xác phương trình x3 + 2021x + 2 = 0 với -1000 ≤x ≤ 1000 với sai số chấp nhận được 10-6, chúng ta sử dụng phương pháp giải nào dưới đây?

[0] Duyệt toàn bộ


Đáp án [100] Chia để trị


[0] Quy hoạch động


[0] Thuật toán đặc thù


[0] Thuật toán trên đồ thị


[0] Đáp án khác
Câu 4143465 Loại câu: QHĐ trên Bitmask

Phương pháp Qui hoạch động trên Bitmask giải bài toán người du lịch cho lời giải thế nào?


[0] Lời giải chấp nhận được (không đảm bảo tính tối ưu)


Đáp án [100] Lời giải tối ưu


[0] Đáp án khác
Câu 4143466 Loại câu: Queue

Cấu trúc dữ liệu Queue cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?


Đáp án [100] vào một đầu, ra đầu còn lại


[0] vào và ra được từ cả hai đầu


[0] vào và ra duy nhất một đầu


[0] không cách nào trong các cách ở đây


[0] đáp án khác
Câu 4143467 Loại câu: quicksort

Trong một phiên bản giải thuật quicksort, người ta dùng một giải thuật \(O(n)\) để tìm phần tử nhỏ thứ \(n/5\) của dãy, và dùng phần tử này làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?

Đáp án [100]

\(O(nlogn)\)

[0]

\(O(n^5logn)\)

[0]

\(O(nlog^5n)\)

[0]

\(O(n^2)\)

[0] Đáp án khác
Câu 4143468 Loại câu: Stack

Cấu trúc dữ liệu Stack cho phép đẩy dữ liệu vào và lấy dữ liệu ra theo cách nào trong các cách sau?


[0] vào một đầu, ra đầu còn lại


[0] vào và ra được từ cả hai đầu


Đáp án [100] vào và ra duy nhất một đầu


[0] không cách nào trong các cách ở đây


[0] đáp án khác
Câu 4143469 Loại câu: BinarySearch (bản sao)

Nếu công thức truy hồi độ phức tạp tính toán của phương pháp tìm kiếm nhị phân (binary search) được biểu diễn dưới dạng \(T(n)=aT(n/b)+O(n^d)\) thì giá trị \(a+b+d\) là bao nhiêu? Ghi ra một số nguyên duy nhất là kết quả đáp án.

Đáp án [100]

3
Câu 4143470 Loại câu: Chia để trị (Khó) - Giải phương trình

Biết rằng hàm số f(x) = x19 - x2 - x + 1 có một nghiệm nằm trong khoảng [0, 1], bạn được yêu cầu lập trình để tìm và điền nghiệm trên với sai số 10-6 vào ô trống.

Đáp án [100]

0.618082
Câu 4143471 Loại câu: Quy hoạch động (Khó) - SubSeq3Max

Cho dãy số nguyên [-9, 17, -16, -50, 19, -26, 28, 8, 12, 14, -45, -5, 31, -23, 11, 41, 45, -8, -23, -14], hãy tìm một đoạn con các phần tử liên tiếp trong dãy sao cho tổng mũ 3 của các phần tử trong đoạn con là lớn nhất và điền giá trị tổng này vào ô trống

Đáp án [100]

179001
Câu 4143472 Loại câu: Chia để trị (Khó) - Số phép nhân trong tính toán đa thức

Xét đa thức p(x) = a0 + a1*x + a2*x2 + a3*x3, trong đó ai! = 0, với mọi i. Số phép nhân tối thiểu cần thiết để tính giá trị của p(x) với đầu vào x bất kỳ?

Đáp án [100] 3


[0] 4


[0] 6


[0] 9


[0] 12


[0] Đáp án khác
Câu 4143473 Loại câu: Số phép nhân tính đa thức (copy)

Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?

Đáp án [100]

4

[0]

5

[0]

8

[0]

10

[0] Đáp án khác
Câu 4143474 Loại câu: Dãy con cực đại - instance 1 (bản sao)

Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.

Cho dãy số 2, 5, -10, 3, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2 . Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?

[0]

7

[0]

14

[0]

20

Đáp án [100]

18

[0] Đáp án khác
Câu 4143475 Loại câu: Dãy con cực đại - instance 2 (bản sao)

Cho dãy số a = a[1], a[2], …, a[n]. Dãy con của dãy a được định nghĩa là dãy a=a[i], a[i+1],...,a[j] (1 <= i <= j <= n), trọng số của dãy con bằng tổng các phần tử của nó.

Cho dãy số 2, 5, -10, 6, 3, 8, -8, -2, 2, 12, -20, 6, 4, -4, 2. Tìm dãy con có trọng số lớn nhất của dãy đó. Hỏi trọng số của dãy con tìm được có giá trị bằng bao nhiêu?

[0]

7

[0]

17

Đáp án [100]

21

[0]

27

[0] Đáp án khác
Câu 4143476 Loại câu: Dãy con giãn cách cực đại - instance 1 (bản sao)

Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 2, 5, 8, 6, 3, 4, 10, 14, 8. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?

[0]

30

Đáp án [100]

31

[0]

32

[0]

33

[0]

34

[0] Đáp án khác
Câu 4143477 Loại câu: Dãy con giãn cách cực đại - instance 2 (bản sao)

Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. Các phần tử 1,2…, 9 có trọng số tương ứng là 6, 4, 9, 2, 5, 9, 10, 14, 6. Hãy chọn ra tập con S các phần tử i1 < i2 < … < ik từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử ij và ij+1 (j = 1, ..., k-1) lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= ij+1 – ij <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con giãn cách cực đại). Hỏi tổng trọng số các phần tử của S là bao nhiêu?

[0]

36

[0]

37

Đáp án [100]

38

[0]

40

[0]

42

[0] Đáp án khác
Câu 4143478 Loại câu: Dãy con giãn cách cực đại - instance 3 (bản sao)

Cho 9 phần tử 1, 2, …, 9 nằm trên 1 đường thẳng, trong đó phần tử i nằm ở tọa độ i. 9 phần tử 1,2…, 9 có trọng số tương ứng là 2, 6, 8, 1, 7, 4, 10, 4, 5. Hãy chọn ra tập con S các phần tử i[1] < i[2] < … < i[k] từ 9 phần tử đã cho sao cho khoảng cách giữa 2 phần tử i[j] và i[j+1] lớn hơn hoặc bằng 2 và nhỏ hơn hoặc bằng 4 (2 <= i[j+1] – i[j] <= 4, còn gọi là điều kiện giãn cách) đồng thời tổng trọng số các phần tử đó là lớn nhất (được gọi là tập con lớn nhất). Hỏi tổng trọng số các phần tử của S là bao nhiêu?

[0]

30

Đáp án [100]

32

[0]

34

[0]

35

[0] Đáp án khác
Câu 4143479 Loại câu: Giải thích kết quả chương trình ngăn xếp 1 (bản sao)


Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)

for i = 10 downto 1 do{
S.PUSH(i);
}
for i = 1 to 4 do {
x = S.POP();
}
x = S.POP();
print(x);

Đáp án [100] 5


[0] 2


[0] 9


[0] 4


[0] Đáp án khác
Câu 4143480 Loại câu: Giải thích kết quả chương trình ngăn xếp 2 (bản sao)


Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 10 do{
S.PUSH(i);
}

for i = 1 to 3 do{
x = S.POP();
}
x = S.POP();
print(x);

[0] 5


Đáp án [100] 7


[0] 6


[0] 4


[0] Đáp án khác
Câu 4143481 Loại câu: Giải thích kết quả chương trình ngăn xếp 3 (bản sao)


Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 5 do{
S.PUSH(i);
}

for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);

[0] 4


Đáp án [100] 3


[0] 2


[0] 5


[0] Đáp án khác
Câu 4143482 Loại câu: Giải thích kết quả chương trình ngăn xếp 4 (bản sao)


Cho S là 1 ngăn xếp (Stack) với 2 thao tác PUSH (đưa một phần tử vào ngăn xếp), POP (lấy ra 1 phần tử từ ngăn xếp). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)
for i = 1 to 7 do{
S.PUSH(i);
}

for i = 1 to 2 do{
x = S.POP();
}
x = S.POP();
print(x);

Đáp án [100] 5


[0] 3


[0] 4


[0] 6


[0] Đáp án khác
Câu 4143483 Loại câu: Giải thích kết quả chương trình Queue 1 (bản sao)


Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)

for i = 1 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);

[0] 1


[0] 4


[0] 6


Đáp án [100] 5


[0] Đáp án khác
Câu 4143484 Loại câu: Giải thích kết quả chương trình Queue 2 (bản sao)


Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)

for i = 3 to 10 do{
Q.PUSH(i);
}
for i = 1 to 4 do{
x = Q.POP();
}
x = Q.POP();
print(x);

[0] 1


[0] 4


[0] 6


Đáp án [100] 7


[0] Đáp án khác
Câu 4143485 Loại câu: Giải thích kết quả chương trình Queue 3 (bản sao)


Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)

for i = 2 to 10 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);

[0] 1


Đáp án [100] 5


[0] 2


[0] 7


[0] Đáp án khác
Câu 4143486 Loại câu: Giải thích kết quả chương trình Queue 4 (bản sao)


Cho Q là 1 hàng đợi (Queue) với 2 thao tác PUSH (đưa một phần tử vào hàng đợi), POP (lấy ra 1 phần tử từ hàng đợi). Hãy cho biết kết quả hiển thị của đoạn chương trình sau đây (mô tả mã giả)

for i = 10 downto 1 do{
Q.PUSH(i);
}
for i = 1 to 3 do{
x = Q.POP();
}
x = Q.POP();
print(x);

[0] 4


[0] 5


[0] 3


Đáp án [100] 7


[0] Đáp án khác
Câu 4143487 Loại câu: Kết quả chương trình đệ quy 1 (bản sao)

Hỏi kết quả của chương trình sau


#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 3*f(n-1) + 2*f(n-2);
else return 2*f(n-1) + 3*f(n-2);
}
int main(){
printf(”%d”,f(5));
}


Đáp án [100] 137


[0] 100


[0] 37


[0] 52


[0] Đáp án khác
Câu 4143488 Loại câu: Kết quả chương trình đệ quy 2 (bản sao)

Hỏi kết quả của chương trình sau


#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n/2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}



[0] 37


[0] 103


Đáp án [100] 11


[0] 42


[0] Đáp án khác
Câu 4143489 Loại câu: Kết quả chương trình đệ quy 3 (bản sao)

Hỏi kết quả của chương trình sau


#include
int f(int n){
if(n <= 1) return 1;
if(n%2 == 0) return 2*f(n-1) + f(n-2);
else return f(n-1) - 2*f(n-2);
}
int main(){
printf(”%d”,f(5));
}




[0] 30


Đáp án [100] 3


[0] 6


[0] 8


[0] Đáp án khác
Câu 4143490 Loại câu: Kết quả chương trình đệ quy 4 (bản sao)

Hỏi kết quả của chương trình sau


#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 0) return f(n-1) + f(n-2);
else return 2*f(n-1) - f(n-2);
}
int main(){
printf(”%d”,f(5));
}





[0] 20


Đáp án [100] 4


[0] 5


[0] 9


[0] Đáp án khác
Câu 4143491 Loại câu: Kết quả chương trình đệ quy 5 (bản sao)

Hỏi kết quả của chương trình sau


#include
int f(int n){
if(n <= 1) return 1;
if(n%3 == 1) return f(n-1) + 2*f(n-2);
else return f(n-1) + f(n-2);
}
int main(){
printf(”%d”,f(4));
}





[0] 10


[0] 4


[0] 6


Đáp án [100] 7


[0] Đáp án khác
Câu 4143492 Loại câu: Khái niệm cơ bản danh sách liên kết 1 (bản sao)


Phát biểu nào sau đây không đúng


Đáp án [100] Các phần tử của danh sách liên kết luôn được cấp phát kế tiếp nhau trong bộ nhớ


[0] Các phần tử của danh sách liên kết không nhất thiết được cấp phát kế tiếp nhau trong bộ nhớ


[0] Không đáp án nào đúng
Câu 4143493 Loại câu: Khái niệm cơ bản danh sách liên kết 2 (bản sao)


Phát biểu ”Ta truy nhập đến các phần tử của danh sách liên kết thông qua chỉ số” là đúng hay sai?


[0] Đúng


Đáp án [100] Sai



Câu 4143494 Loại câu: Khái niệm cơ bản danh sách liên kết 3 (bản sao)


Phát biểu ”Thao tác tìm kiếm một phần tử trên danh sách liên kết có độ phức tạp trong tình huống tồi nhất là O(n) với n là số phần tử của danh sách liên kết” là đúng hay sai?


Đáp án [100] Đúng


[0] Sai



Câu 4143495 Loại câu: Khái niệm cơ bản, độ phức tạp tính toán 1 (bản sao)


Phát biểu ”Thuật toán sắp xếp trộn dựa trên sơ đồ chia để trị” là đúng hay sai?


Đáp án [100] Đúng


[0] Sai
Câu 4143496 Loại câu: Khái niệm cơ bản, độ phức tạp tính toán 2 (bản sao)


Hãy cho biết thuật toán sắp xếp sau đây là thuật toán sắp xếp gì? for k = 1 to n do{
m = k;
for j = k+1 to n do {
if a[m] > a[j] then {
m = j;
}
}
Swap(a[m],a[k]);// đảo hai giá trị a[m] và a[k]
}


[0] Sắp xếp chèn


Đáp án [100] Sắp xếp lựa chọn


[0] Sắp xếp nổi bọt


[0] Sắp xếp vun đống


[0] Đáp án khác
Câu 4143497 Loại câu: Phân tích độ phức tạp tính toán 1 (bản sao)

Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)

f(n){

   s = 1; 

   i = 1;

   While s <= n {
      s = s * 2;
      i++;
   }
}

Đáp án [100] \(O(logn)\)


[0] \(O(n)\)


[0] \(O(nlogn)\)


[0] Đáp án khác
Câu 4143498 Loại câu: Phân tích độ phức tạp tính toán 2 (bản sao)

Hãy cho biết độ phức tạp tính toán (đưa ra đánh giá sát nhất) của hàm f(n) sau đây (mô tả mã giả )

f(n){  

   k = 1;
   for i = 1 to n do{ 

        While  k <=  n and  a[k] < a[i]  do{ 

             k = k + 1;

         } 

   }

}

[0] \(O(nlogn)\)


Đáp án [100] \(O(n)\)


[0] \(O(n^2)\)


[0] Đáp án khác
Câu 4143499 Loại câu: Phân tích độ phức tạp tính toán 3 (bản sao)

Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)

f(n){  
    If  (n <= 1 )  return 0;

    If  n mod 2 = 0 { 

        Return 4*f(n/2) + 3n - 2;

    }else{ 

        Return 2*f(n/2) + 2n + 5; 

    }

}

[0] \(O(log(logn))\)


[0] \(O(n)\)


[0] \(O(n^\frac {1}{2})\)


Đáp án [100] \(O(logn)\)


[0] Đáp án khác
Câu 4143500 Loại câu: Phân tích độ phức tạp tính toán 4 (bản sao)

Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)

f(n){  
    s = 1;

    a = 2;
    i = 1;
    While  s <= n {
        s = s * a;
        a = a*a;
        i = i + 1;

    }  
} 

Đáp án [100] \(O(log(logn))\)


[0] \(O(n)\)


[0] \(O(n^\frac {1}{2})\)


[0] \(O(nlogn)\)


[0] Đáp án khác
Câu 4143501 Loại câu: Phân tích độ phức tạp tính toán 5 (bản sao)

Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)
f(n){

   s = 0;
   a = 1;
   i = 1;
   While   s  <= n {
       s = s + a;
       a = 2*a;
       i++;
    }

}

Đáp án [100] \(O(logn)\)


[0] \(O(n)\)


[0] \(O(n^\frac {1}{2})\)


[0] \(O(nlogn)\)


[0] Đáp án khác
Câu 4143502 Loại câu: Phân tích độ phức tạp tính toán 6 (bản sao)

Hãy cho biết độ phức tạp tính toán của hàm f(n) sau đây (mô tả mã giả)

f(n){

   s = 0;

   a = 1;
   i = 1;
   While s <= n {
      s = s + a;
      a = a + 1;
      i = i + 1;
   }

}

[0] \(O(logn)\)


[0] \(O(n)\)


Đáp án [100] \(O(n^\frac {1}{2})\)


[0] \(O(nlogn)\)


[0] Đáp án khác
Câu 4143503 Loại câu: Xây dựng tháp - instance 1 (bản sao)

Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 2 x 4 x 2. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d

[0]

9

[0]

8

Đáp án [100]

12

[0]

13

[0]

10

[0]

11

[0] Đáp án khác
Câu 4143504 Loại câu: Xây dựng tháp - instance 2 (bản sao)

Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 5 và 4 x 4 x 3. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d

[0]

10

[0]

9

Đáp án [100]

11

[0]

13

[0]

12

[0]

14

[0] Đáp án khác
Câu 4143505 Loại câu: Xây dựng Tháp - instance 3 (bản sao)

Cho các khối lập phương (thuộc tính là chiều dài, rộng và chiều cao) thuộc 3 cấu hình: 3 x 2 x 3, 3 x 4 x 8 và 3 x 3 x 5. Giả thiết số lượng khối lập phương thuộc mỗi cấu hình là vô hạn. Hỏi có thể chọn và xếp các khối lập phương thành 1 tòa tháp có chiều cao lớn nhất là bao nhiêu (các khối lập phương có thể xoay theo các góc khác nhau) với điều kiện kích thước của khối nằm trên a x b phải nhỏ hơn hẳn kích thước của khối nằm dưới c x d, tức là a < c và b < d

[0]

12

[0]

13

Đáp án [100]

14

[0]

15

[0]

16

[0] Đáp án khác
Câu 4143506 Loại câu: Chia kẹo - instance 1

Có bao nhiêu cách chia 20 cái kẹo cho 9 em mà em nào cũng có kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

75582
Câu 4143507 Loại câu: Chia kẹo - instance 2

Có bao nhiêu cách chia 21 cái kẹo cho 8 em mà em nào cũng có kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

77520
Câu 4143508 Loại câu: Chia kẹo - instance 3

Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà em nào cũng có kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

31824
Câu 4143509 Loại câu: Chia kẹo - instance 4

Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà em nào cũng có kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

50388
Câu 4143510 Loại câu: Chia kẹo - instance 5

Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà em nào cũng có kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

27132
Câu 4143511 Loại câu: Chia kẹo khó - instance 1

Có bao nhiêu cách chia 20 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

796510
Câu 4143512 Loại câu: Chia kẹo khó - instance 2

Có bao nhiêu cách chia 20 cái kẹo cho 7 em mà mỗi em có không quá 10 kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

195195
Câu 4143513 Loại câu: Chia kẹo khó - instance 3

Có bao nhiêu cách chia 19 cái kẹo cho 8 em mà mỗi em có không quá 10 kẹo?

(Gợi ý: có thể sử dụng phương pháp lập trình sinh ra tất cả các khả năng chia có thể để đếm)

Đáp án [100]

606320
Câu 4150797 Loại câu: Đặc điểm của quay lui

Phát biểu nào sau đây về quy lui (backtracking) là đúng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

Bài toán sinh tất cả các xâu nhị phân có độ dài cho trước không thể giải được bằng thuật toán quay lui

Đáp án [100]

Thuật toán quay lui có thể tìm ra giải pháp tối ưu cho bài toán tối ưu hóa tổ hợp

[0]

Thuật toán quay lui luôn có độ phức tạp thời gian tính toán đa thức

[0]

Thuật toán quay lui không thể tìm thấy bất kỳ lời giải tối ưu nào cho một bài toán tối ưu hóa tổ hợp

[0]

Đáp án khác

Câu 4150798 Loại câu: Đặc điểm của BFS

Cho đồ thị vô hướng G = (V, E), với V là tập đỉnh và E là tập cạnh. Ký hiệu, A[x] là tập các đỉnh kề với đỉnh x, với mọi x thuộc V. 

Cho một hàm (được miêu tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào: 

process(s, t){

  Init an empty queue Q;

  for x in V do 

    d[x] = -1;

  Q.push(s);// push an element into the queue Q

  d[s] = 0;

  while Q not empty do{

    u = Q.pop();// pop an element out of the queue Q

    for v in A(u) do{

      if d[v] = -1 then{

        Q.push(v);

        d[v] = d[u] + 1;    

      }

    }    

  }  

  return d[t];

}

Phát biểu nào dưới đây là đúng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G

[0]

Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi ngắn nhất từ s tới t trên G

[0]

Nếu G là liên thông thì hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G

[0]

Hàm trên sẽ trả ra độ dài (số lượng cạnh) của đường đi dài nhất từ s tới t trên G

[0]

Đáp án khác

Câu 4150799 Loại câu: Nhận diện thuật toán cho bài toán subset sum

Cho đoạn chương trình dưới đây (miêu tả bằng mã giả), trong đó mảng a (các phần tử được đánh chỉ số từ 1 tới n), các biến toàn cục (global variables) n, m, T, cnt (a, n, m là tham số đầu vào)

solve(k){

   for v = 0 to 1 do{

      T = T + v*a[i];

      if k = n then{

         if T = m then 

            cnt = cnt + 1;

      }else 

         solve(k+1);      

   }

}

main{

    T = 0; 

    cnt = 0;

    solve(1);

    print(cnt);

}

Phát biểu nào dưới đây là đúng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

Chương trình tính số cách chọn các phần tử sao cho tổng các phần tử được chọn bằng m

[0]

Chương trình kiểm tra xem tổng các phần tử của a có bằng m không?

[0]

Chương trình tính số lần giá trị m xuất hiện trong mảng a

Đáp án [100]

Đáp án khác

Câu 4150800 Loại câu: Nhận diện đúng BFS

Cho đồ thị vô hướng G = (V, E), trong đó V là tập đỉnh và E là tập cạnh. Ký hiệu A[x] là tập các đỉnh kề với đỉnh x (với mọi x thuộc V).

Cho hàm (được mô tả bằng mã giả phía dưới) nhận 2 đỉnh s và t (s, t thuộc V) là tham số đầu vào.

process(s, t){

    Init an empty queue Q;

    for x in V do 

        d[x] = -1;

    Q.push(s);// push an element into the queue Q

    d[s] = 0;

    while Q not empty do{

        u = Q.pop();// pop an element out of the queue Q

        print(u);

        for v in A(u) do{

            Q.push(v);

            d[v] = d[u] + 1;    

        }    

    }  

    return d[t];

}

Phát biểu nào sau đây là đúng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

Đáp án khác

[0]

Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều rộng

[0]

Chương trình duyệt qua các đỉnh của đồ thị (mỗi đỉnh 1 lần) theo thứ tự Tìm kiếm theo chiều sâu

[0]

Chương trình kết thúc và trả về độ dài (số cạnh) của đường đi ngắn nhất từ s tới t trên G

Câu 4150801 Loại câu: Hiển thị kết quả Max Independence Set trên một cây

Cho một cây T = (V, E), trong đó V = {1,2,3,4,5,6,7,8,9,10,11,12,13} là tập các đỉnh và E = {(1,2), (1,12), (1,13), (2,3), (2,4), (3,7), (3,8), (3,9), (4,5), (4,6), (5,10), (5,11)} là tập các cạnh. Các đỉnh 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 lần lượt có trọng số 8, 6, 9, 1, 9, 2, 10, 2, 4, 3, 2, 5, 7. Tìm một tập con S các đỉnh trong V có tổng các trọng số lớn nhất sao cho 2 đỉnh bất kỳ trong S không kề nhau trên T. Tổng các trọng số các đỉnh trong S bằng bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

37

[0]

35

[0]

38

[0]

39

[0]

43

[0]

45

[0]

46

[0]

Đáp án khác

Câu 4150802 Loại câu: Hiểu thị kết quả thuật toán quay lui

Cho đoạn chương trình được miêu tả bởi một đoạn mã giả dưới đây, trong đó hàm P nhận một mảng a, n, W, T, k như tham số (thành phần của mảng a được đánh chỉ số từ 1 tới n) và cnt là một biến toàn cục.

P(a, n, W, T, k){

    for v = 0 to 1 do {

        if (k = n) then{

             if (T + v*a[k] = W) then cnt = cnt + 1;

        }else 

             P(a, n, W, T + v*a[k], k+1);

    }

}

Main { // main function

      a = {2,3,6,7,4,5}; // array indexed from 1 to 6

      cnt = 0;

      P(a, 6, 12, 0, 1);

      print(cnt); // print the value cnt to the screen

}

Giá trị của cnt được in ra màn hình trong hàm Main là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

4

[0]

2

[0]

3

[0]

5

[0]

6

[0]

8

[0]

9

[0]

Đáp án khác

Câu 4150803 Loại câu: Hiển thị kết quả mô phỏng Min-Heap

Mỗi phần tử của một Min-Heap (được biểu diễn bởi một cây đầy đủ) có hai trường (id, k), trong đó id là định danh và k là khóa của phần tử. Min-Heap có các hàm (operations) sau:

  • insertHeap(id, k): Chèn 1 phần tử với định danh id và khóa k vào trong Min-Heap
  • deleteMin(): Trả về phần tử (id, k) có khóa nhỏ nhất và xóa phần tử này ra khỏi Min-Heap
  • updateKey(id, k): Cập nhật phần tử có định danh id với giá trị khóa mới k

Hiện hiện một chuỗi các thao tác sau trên Min-Heap:

  •     insertHeap(1,4)
  •     insertHeap(2,9)
  •     insertHeap(3,3)
  •     insertHeap(4,7)
  •     insertHeap(5,6)
  •     insertHeap(6,1)
  •     insertHeap(7,2)
  •     insertHeap(8,5)
  •     insertHeap(9,10)
  •     deleteMin()

Phát biểu nào dưới đây là đúng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

Phần tử có định danh 4 là con phải của phần tử có định danh 8

[0]

Phần tử có định danh 4 là con trái của phần tử có định danh 8

[0]

Phần tử có định danh 2 là con phải của phần tử có định danh 8

[0]

Phần tử có định danh 2 là con trái của phần tử có định danh 8

[0]

Phần tử có định danh 1 là con phải của phần tử có định danh 7

[0]

Phần tử có định danh 1 là con trái của phần tử có định danh 7

[0]

Đáp án khác

Câu 4150804 Loại câu: Số phép nhân tính đa thức (copy)

Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

3

[0]

4

[0]

6

[0]

9

[0]

Đáp án khác

Câu 4150805 Loại câu: Số phép nhân tính đa thức (copy) (copy)

Cho đa thức \(p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 \), trong đó \(a_i \neq 0\), với mọi \(i\). Hỏi số phép toán nhân tối thiểu để tính giá trị của p đối với một đầu vào \(x\) là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

4

[0]

5

[0]

8

[0]

10

[0]

Đáp án khác

Câu 4150806 Loại câu: Greedy 1 (copy)

Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:

  • Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian bắt đầu \(S_j\);
  • Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.

Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?


[-50]

\(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)

Đáp án [50]


\(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)

Đáp án [50]


\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)

[-50]

\(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)

[0]

Đáp án khác

Câu 4150807 Loại câu: Greedy 2 (copy)

Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:

  • Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của thời gian kết thúc \(F_j\);
  • Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.

Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?


Đáp án [25] \(S_1=3, S_2=7, S_3 =1, F_1=5, F_2=10, F_3=15\)


Đáp án [25] \(S_1=3, S_2=7, S_3 =4, F_1=5, F_2=10, F_3=15\)


Đáp án [25] \(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=7\)


Đáp án [25] \(S_1=3, S_2=7, S_3 =2, F_1=5, F_2=10, F_3=8\)


[0]

Đáp án khác

Câu 4150808 Loại câu: Greedy 3 (copy)

Có \(n=3\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:

  • Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của tổng thời gian thực hiện công việc \(F_j - S_j\);
  • Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.

Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?


Đáp án [50]


\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=7\)

Đáp án [50]


\(S_1=5, S_2=2, S_3 =6, F_1=7, F_2=5, F_3=15\)

[-50]

\(S_1=1, S_2=6, S_3 =4, F_1=5, F_2=10, F_3=6\)

[-50]

\(S_1=1, S_2=6, S_3 =5, F_1=5, F_2=10, F_3=7\)

[0]

Đáp án khác

Câu 4150809 Loại câu: Greedy 4 (copy)

Có \(n=9\) công việc, công việc \(j\) bắt đầu tại \(S_j\) và kết thúc tại \(F_j\). Hai công việc là phù hợp với nhau nếu chúng không chồng lên nhau. Yêu cầu: Tìm tập con nhiều nhất các công việc đôi một phù hợp với nhau.
Xét thuật toán tham lam sau:

  • Với mỗi công việc \(j\), tính \(C_j\) là số lượng công việc không tương thích với \(j\). Sắp xếp các công việc theo thứ tự ưu tiên tăng dần của \(C_j\);
  • Tại mỗi bước, chọn lần lượt công việc theo thứ tự ưu tiên đã sắp xếp mà phù hợp với tất cả các công việc đã chọn.

Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?


Đáp án [50]


\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)

Đáp án [50]


\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =4, F_8=6, S_9 =6, F_9=8\)

[-50]

\(S_1=2, F_1=4, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =7, F_4=9, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)

[-50]

\(S_1=1, F_1=3, S_2=3, F_2=5, S_3 =5, F_3=7, S_4 =6, F_4=8, S_5 =2, F_5=4, S_6 =2, F_6=4, S_7 =4, F_7=6, S_8 =6, F_8=8, S_9 =6, F_9=8\)

[0]

Đáp án khác

Câu 4150810 Loại câu: Greedy 1 (copy)

Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=19\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:

  • Sắp xếp các đồ vật theo thứ tự không tăng của giá trị;
  • Lần lượt xét các đồ vật theo thứ tự đã sắp, và xếp đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\)).
Hỏi những bộ giá trị nào KHÔNG cho lời giải tối ưu với thuật toán trên?


Đáp án [50]


\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=15\)

[-50]

\(C_1=16, C_2=8, C_3 =20, W_1=6, W_2=10, W_3=13\)

Đáp án [50]


\(C_1=16, C_2=8, C_3 =20, W_1=7, W_2=10, W_3=14\)

[-50]

\(C_1=16, C_2=8, C_3 =20, W_1=5, W_2=10, W_3=14\)

[0]

Đáp án khác

Câu 4150811 Loại câu: Greedy 2 (copy)

Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=11\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:

  • Sắp xếp các đồ vật theo thứ tự không giảm của trọng lượng;
  • Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Hỏi những bộ giá trị nào CHO lời giải tối ưu với thuật toán trên?


[-50]

\(C_1=15, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)

Đáp án [50]


\(C_1=16, C_2=27, C_3 =11, W_1=5, W_2=10, W_3=6\)

Đáp án [50]


\(C_1=15, C_2=27, C_3 =13, W_1=5, W_2=10, W_3=6\)

[-50]

\(C_1=14, C_2=27, C_3 =12, W_1=5, W_2=10, W_3=6\)

[0]

Đáp án khác

Câu 4150812 Loại câu: Greedy 3 (copy)

Có \(n=3\) đồ vật. Đồ vật \(i\) có trọng lượng \(W_i\) và giá trị \(C_i\), \(i = 1, \ldots, n\). Yêu cầu: Tìm cách chất các đồ vật này vào cái túi có dung lượng là \(b=4\) sao cho tổng trọng lượng của các đồ vật được chất vào túi là không quá b, đồng thời tổng giá trị của chúng là lớn nhất.
Xét thuật toán tham lam sau:

  • Sắp xếp các đồ vật theo thứ tự không tăng của giá trị một đơn vị trọng lượng (\(C_i /W_i\)), nghĩa là \[\frac {C_{i_1}}{W_{i_1}} \ge \frac {C_{i_2}}{W_{i_2}} \ge \ldots\le \frac {C_{i_n}}{W_{i_n}};\]
  • Lần lượt xét các đồ vật theo thứ tự đã sắp, và chất đồ vật đang xét vào túi nếu như dung lượng còn lại của cái túi đủ chứa nó (tức là tổng trọng lượng của các đồ vật đã xếp vào túi và trọng lượng của đồ vật đang xét là không vượt quá \(b\))
Hỏi những bộ giá trị nào KHÔNG CHO lời giải tối ưu với thuật toán trên?


[-50]

\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=2\)

Đáp án [50]


\(C_1=8, C_2=15, C_3=8, W_1=2, W_2=4, W_3=3\)

[-50]

\(C_1=8, C_2=15, C_3=8, W_1=3, W_2=4, W_3=1\)

Đáp án [50]


\(C_1=8, C_2=10, C_3=8, W_1=2, W_2=4, W_3=3\)

[0]

Đáp án khác

Câu 4150813 Loại câu: Inter-City BUS - instance 1 (copy)

Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:

  • Thành phố 1 nối với thành phố 2
  • Thành phố 1 nối với thành phố 5
  • Thành phố 3 nối với thành phố 5
  • Thành phố 3 nối với thành phố 6
  • Thành phố 4 nối với thành phố 5
  • Thành phố 4 nối với thành phố 6

Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:

  • Bus từ thành phố 1 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 2 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
  • Bus từ thành phố 3 có giá vé là 90 và có thể đi đến nhiều nhất 1 thành phố khác
  • Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 3 thành phố khác
  • Bus từ thành phố 5 có giá vé là 20 và có thể đi đến nhiều nhất 1 thành phố khác
  • Bus từ thành phố 6 có giá vé là 20 và có thể đi đến nhiều nhất 5 thành phố khác

Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.

Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

50

[0]

60

Đáp án [100]

70

[0]

80

[0]

90

[0]

Đáp án khác

Câu 4150814 Loại câu: Inter-City BUS - instance 2 (copy)

Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:

  • Thành phố 1 nối với thành phố 2
  • Thành phố 1 nối với thành phố 5
  • Thành phố 3 nối với thành phố 5
  • Thành phố 3 nối với thành phố 6
  • Thành phố 4 nối với thành phố 5
  • Thành phố 4 nối với thành phố 6

Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:

  • Bus từ thành phố 1 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 1 thành phố khác
  • Bus từ thành phố 3 có giá vé là 40 và có thể đi đến nhiều nhất 3 thành phố khác
  • Bus từ thành phố 4 có giá vé là 60 và có thể đi đến nhiều nhất 4 thành phố khác
  • Bus từ thành phố 5 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác

Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.

Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

40

Đáp án [100]

50

[0]

60

[0]

70

[0]

80

[0]

Đáp án khác

Câu 4150815 Loại câu: Inter-City BUS - instance 3 (copy)

Có 6 thành phố 1, 2, 3, 4, 5, 6. Giữa 6 thành phố này có các con đường nối giữa chúng bao gồm:

  • Thành phố 1 nối với thành phố 2
  • Thành phố 1 nối với thành phố 5
  • Thành phố 3 nối với thành phố 5
  • Thành phố 3 nối với thành phố 6
  • Thành phố 4 nối với thành phố 5
  • Thành phố 4 nối với thành phố 6

Từ mỗi thành phố sẽ có 1 tuyến bus để đi đến các thành phố khác dọc theo các con đường nối nêu trên, cụ thể như sau:

  • Bus từ thành phố 1 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 2 có giá vé là 30 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 3 có giá vé là 20 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 4 có giá vé là 50 và có thể đi đến nhiều nhất 2 thành phố khác
  • Bus từ thành phố 5 có giá vé là 40 và có thể đi đến nhiều nhất 4 thành phố khác
  • Bus từ thành phố 6 có giá vé là 10 và có thể đi đến nhiều nhất 2 thành phố khác

Để đi từ 1 thành phố a đến 1 thành phố b khác, có thể phải đi nhiều tuyến bus: lên bus của thanh phố a đi một mạch đến thành phố i1, sau đó lên bus của thành phố i1 và đi một mạch đến thành phố i2, ... cuối cùng lên bus của thành phố ik và đi một mạch đến thành phố b.

Hỏi cách đi tối ưu từ thành phố 1 đến thành phố 6 với số tiền ít nhất phải bỏ ra mua vé là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

10

[0]

20

Đáp án [100]

30

[0]

40

[0]

50

[0]

Đáp án khác

Câu 4150816 Loại câu: Make Span - instance 1 (copy)

Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 5, 2, 3, 7, 2, 3, 6, 3. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

26

[0]

27

Đáp án [100]

28

[0]

29

[0]

30

[0]

Đáp án khác

Câu 4150817 Loại câu: MakeSpan - instance 2 (copy)

Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 7, 1, 4, 2, 7, 6, 5, 3, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

24

[0]

25

[0]

26

[0]

27

[0]

28

[0]

Đáp án khác

Câu 4150818 Loại câu: MakeSpan - Schedule (copy)

Có 9 công việc 1, 2, …, 9 với thời gian hoàn thành tương ứng là 5, 3, 1, 2, 6, 4, 3, 1, 4. Giữa các công việc có quan hệ về thứ tự thực hiện, được biểu diễn bởi một tập các bộ (i,j) trong đó công việc j chỉ có thể được thực hiện sau khi công việc i được thực hiện xong. Quan hệ về thứ tự thực hiện đó được thể hiện trong tập sau {(1,3), (1,5), (1,6), (2,1), (2,3), (3,5), (4,1), (4,2), (4,6), (5,8), (7,9), (9,5), (9,8)}.
Hỏi thời gian nhanh nhất hoàn thành tất cả n công việc là bao nhiêu?


[0] 16


Đáp án [100] 18


[0] 19


[0] 23


[0]

Đáp án khác

Câu 4150819 Loại câu: Bài toán nhân viên chăm sóc khách hàng 1 (copy)

Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho nhân viên chăm sóc khách hàng này.
Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


Đáp án [100] NP-khó


[0] NP-đầy đủ


[0] P


[0]

Đáp án khác

Câu 4150820 Loại câu: Bài toán nhân viên chăm sóc khách hàng 2 (copy)

Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của \(n\) khách hàng mỗi khách đúng một lần để bảo trì sản phẩm cho khách hàng và quay trở lại công ty mình. Cho trước chi phí đi lại trực tiếp giữa các địa điểm và giữa công ty và các địa điểm. Hỏi có tồn tại một hành trình cho nhân viên chăm sóc khách hàng này với chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


[0] NP-khó


Đáp án [100] NP-đầy đủ


[0] P


[0]

Đáp án khác

Câu 4150821 Loại câu: Bài toán nhân viên chăm sóc khách hàng 3 (copy)

Một nhân viên chăm sóc khách hàng xuất phát từ công ty phải đến địa điểm của một khách hàng để bảo trì sản phẩm của công ty và quay trở lại công ty mình sau khi xong việc. Có \(n\) vị trí trong thành phố 1,2,..,\(n\), địa điểm công ty là vị trí số 1 và địa điểm khách hàng là vị trí số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) vị trí này.
Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho nhân viên chăm sóc khách hàng này đến địa điểm khách hàng và quay trở về công ty sau khi xong việc. Hành trình có thể đi qua các vị trí trung gian.
Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


[0] NP-khó


[0] NP-đầy đủ


Đáp án [100] P


[0]

Đáp án khác

Câu 4150822 Loại câu: Bài toán thương nhân 1 (copy)

Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hãy tìm hành trình có tổng chi phí là nhỏ nhất cho thương nhân đó.
Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


Đáp án [100] NP-khó


[0] NP-đầy đủ


[0] P


[0]

Đáp án khác

Câu 4150823 Loại câu: Bài toán thương nhân 2 (copy)

Một thương nhân muốn tìm hiểu thị trường của \(n\) thành phố, ông ta xuất phát tại 1 thành phố, muốn đi qua \(n-1\) thành phố còn lại, mỗi thành phố đúng 1 lần và quay trở lại thành phố xuất phát. Cho trước chi phí đi lại trực tiếp giữa các thành phố, hỏi có tồn tại một hành trình cho thương nhân này có chi phí không quá \(k\) hay không?
Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


[0] NP-khó


Đáp án [100] NP-đầy đủ


[0] P


[0]

Đáp án khác

Câu 4150824 Loại câu: Bài toán thương nhân 3 (copy)

Một thương nhân ở thành phố A muốn tìm hiểu thị trường ở thành phố B. Có \(n\) thành phố 1,2,..,\(n\), thành phố A ở thành phố số 1 và thành phố B là thành phố số \(n\). Biết trước chi phí đi lại trực tiếp giữa \(n\) thành phố. Yêu cầu: Hãy tìm một hành trình có chi phí nhỏ nhất cho thương nhân này đi từ thành phố A đến thành phố B và quay trở về thành phố B sau khi xong việc. Hành trình có thể đi qua các thành phố trung gian trong số \(n\) thành phố.

Lớp bài toán nào là chính xác nhất cho bài toán trên?


[0] NP


[0] NP-khó


[0] NP-đầy đủ


Đáp án [100] P


[0]

Đáp án khác

Câu 4150825 Loại câu: Đong nước - instance 1 (copy)

Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:

  • Đổ nước vào đầy bình 1

  • Đổ nước vào đầy bình 2

  • Đổ hết nước từ bình 1 ra ngoài

  • Đổ hết nước từ bình 2 ra ngoài

  • Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)

  • Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)

Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:

  • B1: Đổ nước vào đầy bình 1

  • B2: Đổ nước từ bình 1 sang bình 2

  • B3: Đổ nước vào đầy bình 1

  • B4: Đổ nước từ bình 1 sang bình 2

ta sẽ thu được 4 lít nước ở bình 1.



Với a = 10, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

3

Đáp án [100]

4

[0]

6

[0]

Đáp án khác

Câu 4150826 Loại câu: Đong nước - instance 2 (copy)

Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:

  • Đổ nước vào đầy bình 1

  • Đổ nước vào đầy bình 2

  • Đổ hết nước từ bình 1 ra ngoài

  • Đổ hết nước từ bình 2 ra ngoài

  • Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)

  • Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)

Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:

  • B1: Đổ nước vào đầy bình 1

  • B2: Đổ nước từ bình 1 sang bình 2

  • B3: Đổ nước vào đầy bình 1

  • B4: Đổ nước từ bình 1 sang bình 2

ta sẽ thu được 4 lít nước ở bình 1.



Với a = 7, b = 5, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 3 lít ở 1 trong 2 bình là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

4

[0]

5

[0]

6

[0]

Không có phương án nào thực hiện được

Câu 4150827 Loại câu: Đong nước - instance 3 (copy)

Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:

  • Đổ nước vào đầy bình 1

  • Đổ nước vào đầy bình 2

  • Đổ hết nước từ bình 1 ra ngoài

  • Đổ hết nước từ bình 2 ra ngoài

  • Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)

  • Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)

Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:

  • B1: Đổ nước vào đầy bình 1

  • B2: Đổ nước từ bình 1 sang bình 2

  • B3: Đổ nước vào đầy bình 1

  • B4: Đổ nước từ bình 1 sang bình 2

ta sẽ thu được 4 lít nước ở bình 1.



Với a = 3, b = 8, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 6 lít ở 1 trong 2 bình là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

2

[0]

3

Đáp án [100]

4

[0]

5

[0]

Đáp án khác

Câu 4150828 Loại câu: Đong nước - instance 4 (copy)

Có 2 bình, bình 1 dung tích là a lít và bình 2 dung tích là b lít. Có 1 bể chứa vô hạn nước. Mỗi bước có thể thực hiện 1 trong số các hành động sau:

  • Đổ nước vào đầy bình 1

  • Đổ nước vào đầy bình 2

  • Đổ hết nước từ bình 1 ra ngoài

  • Đổ hết nước từ bình 2 ra ngoài

  • Đổ nước từ bình 1 sang bình 2 (đổ đến khi bình 2 đầy hoặc bình 1 rỗng)

  • Đổ nước từ bình 2 sang bình 1 (đổ đến khi bình 1 đầy hoặc bình 2 rỗng)

Cần thực hiện ít nhất các bước để thu được đúng c lít nước ở 1 trong 2 bình. Ví dụ a = 6, b = 8 và c = 4, số bước cần thực hiện ít nhất là 4 bước như sau:

  • B1: Đổ nước vào đầy bình 1

  • B2: Đổ nước từ bình 1 sang bình 2

  • B3: Đổ nước vào đầy bình 1

  • B4: Đổ nước từ bình 1 sang bình 2

ta sẽ thu được 4 lít nước ở bình 1.



Với a = 2, b = 9, hỏi số bước cần thực hiện ít nhất để thu được lượng nước là 5 lít ở 1 trong 2 bình là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

3

Đáp án [100]

4

[0]

5

[0]

Không có phương án thực hiện

Câu 4150829 Loại câu: Bellman-Ford, dạng đồ thị (copy)

Thuật toán Bellman-Ford tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị có trọng số luôn tìm được lời giải tối ưu trong các trường hợp đồ thị nào sau đây?


[-50]

Đồ thị tổng quát

Đáp án [25] Đồ thị không chứa chu trình âm


Đáp án [25] Đồ thị không có cạnh trọng số âm


Đáp án [25] Đồ thị có hướng không có chu trình DAG


Đáp án [25] Cây


[-50]

Đồ thị hai phía

[0]

Đáp án khác

Câu 4150830 Loại câu: Phép qui dẫn (copy)


Những mệnh đề nào sau đây là ĐÚNG?


Đáp án [50]


Nếu \(A \in NP\)-khó và \(A\prec B\), thì \(B \in NP\)-khó

[-50]

Nếu \(A \in NP\)-khó và \(B\prec A\), thì \(B \in NP\)-khó

[-50]

Nếu \(A \in P\) và \(A\prec B\), thì \(B \in P\)

Đáp án [50]


Nếu \(A \in P\) và \(B\prec A\), thì \(B \in P\)

[0]

Không đáp án nào đúng

Câu 4150831 Loại câu: Phương pháp giải (copy)

Những phương pháp nào thường được sử dụng để đưa ra lời giải chấp nhận được mà không đảm bảo tính tối ưu trong thời gian đa thức cho bài toán thuộc lớp NP-khó?


Loại: -25

Nhánh cận
Loại: 20

Tham lam
Loại: -25

Chia để trị
Loại: -25

Qui hoạch động
Loại: 20

Heuristic
Loại: 20

Meta-heuristic
Loại: 20

Học tăng cường
Loại: 20

Thuật toán xấp xỉ
Loại: -25

Tất cả các phương pháp liệt kê ở đây

[0]

Không đáp án nào đúng

Câu 4150832 Loại câu: TSP-Lớp bài toán (copy)

Bài toán người du lịch với yêu cầu tối thiểu hoá chi phí hành trình của người du lịch thuộc lớp bài toán nào?


[0] NP


Đáp án [100] NP-khó


[0] NP-đầy đủ


[0] P


[0]

Đáp án khác

Câu 4150833 Loại câu: TSP-Phương pháp giải (copy)

Những phương pháp nào có thể giải bài toán người du lịch cho lời giải chấp nhận được?


[0] Nhánh cận


[0] Tham lam


[0] Qui hoạch động


[0] Heuristic


[0] Meta-heuristic


[0] Học tăng cường


Đáp án [100] Tất cả các phương pháp trên
Câu 4150834 Loại câu: Tương quan giữa các lớp bài toán (copy)


Những mối quan hệ nào sau đây là CHẮC CHẮN ĐÚNG?


Đáp án [25] \(P \subseteq NP\)


Đáp án [25] \(NPC \subseteq NP\)


Loại: -12.5

\(P \subset NP\)
Loại: -12.5

\(P \neq NP\)
Loại: -12.5

\(P = NP\)
Loại: -12.5

\(NPC = NP\)
Loại: -12.5

\(NPC \subset NP\)
Loại: -12.5

\(NPC \neq NP\)

Đáp án [25] \(NPC \subset NP\)-khó


Đáp án [25] \(NP\)-khó \(\cap NP = NPC\)


Loại: -12.5

\(NP \subset NP\)-khó
Loại: -12.5

\(P \neq NP\)-khó

[0]

Đáp án khác

Câu 4150835 Loại câu: Thuật toán Người thu ngân (copy)

Thuật toán Người thu ngân có cho lời giải tối ư với các đồng tiền mệnh giá 1xu, 5xu, 10xu, 25xu và 100xu không?


Đáp án [100]

true

Có

[0]

false

Không
Câu 4150836 Loại câu: Tập độc lập trên đồ thị hai phía

Cho đồ thị hai phía $G=(X\cup Y, E)$ với $|X|=${m}, $|Y|=${n}, $|E|=${k}, và lực lượng cặp ghép lớn nhất của $G$ là {s}. Hãy tính lực lượng tập độc lập lớn nhất của $G$.

Đáp án [100]

{n}+{m}-{s}+0*{k} 1 1 0 shared
n
calculated uniform 10 100 0 10 1 55 2 62 3 62 4 80 5 59 6 75 7 57 8 79 9 58 10 15 10 shared
m
calculated uniform 10 100 0 10 1 19 2 74 3 19 4 78 5 26 6 44 7 67 8 74 9 58 10 67 10 shared
s
calculated uniform 1 100 0 10 1 18 2 56 3 17 4 77 5 22 6 42 7 41 8 66 9 58 10 11 10 private
k
calculated uniform 1 100 0 10 1 19 2 57 3 18 4 85 5 35 6 75 7 42 8 71 9 58 10 27 10
Câu 4150837 Loại câu: quicksort

Trong một phiên bản giải thuật quicksort dùng phần tử ở vị trí thứ n/5 làm phần tử chốt. Hỏi độ phức tạp của giải thuật quicksort này trong trường hợp tồi nhất là bao nhiêu?

[0]

\(O(nlogn)\)

[0]

\(O(n^5logn)\)

[0]

\(O(nlog^5n)\)

Đáp án [100]

\(O(n^2)\)

[0] Đáp án khác
Câu 4150838 Loại câu: Dãy con chung dài nhất - instance 1 (bản sao) (bản sao)

Cho dãy số a = a1, a2, …, an. Dãy con của dãy a được định nghĩa là dãy thu được bằng cách loại bỏ một số phần tử của a.

Cho dãy a = 1, 2, 4, 5, 7, 8, 9, 2, 5, 6 và b = 2, 3, 1, 5, 4, 6, 8, 7, 8, 3. Hỏi dãy số dài nhất (tính theo số phần tử) vừa là dãy con của a vừa là dãy con của b có số phần tử bằng bao nhiêu?

[0]

3

Đáp án [100]

4

[0]

5

[0]

6

[0] Đáp án khác
Câu 4150852 Loại câu: Tính chất biểu diễn 1

Nhận định nào dưới đây là đúng khi so sánh biểu diễn đồ thị theo danh sách kề với biểu diễn đồ thị theo ma trận kề?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

Biểu diễn theo danh sách kề sẽ tiết kiệm bộ nhớ hơn cho những ma trận thưa

[0]

DFS và BFS có thể thực hiện trong O(V+E) nếu sử dụng biểu diễn theo danh sách kề. Trong khi đó, nếu biểu diễn theo ma trận kề thì các thao tác này có độ  phức tạp O(V2). Trong đó V, E lần lượt là số lượng đỉnh và cạnh của đồ thị.

[0]

Thêm một đỉnh vào đồ thị sẽ dễ dàng hơn khi biểu diễn theo danh sách kề so với biểu diễn đồ thị theo ma trận kề

Đáp án [100]

Tất cả các đáp án trên

Câu 4150853 Loại câu: Tồn tại đồ thị

Dãy bậc của một đơn đồ thị là dãy bậc của các đỉnh của đồ thị đó được sắp xếp giảm dần. Dãy nào sau đây không thể là dãy bậc của đồ thị nào đó?

I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1


Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

II và IV

[0]

I và II

[0]

III và IV

[0]

IV

[0]

Đáp án khác

Câu 4150854 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prim

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

gc

Đáp án [100]

cg

Đáp án [100]

c-g

Đáp án [100]

g-c

Câu 4150855 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prime

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

df

Đáp án [100]

fd

Đáp án [100]

d-f

Đáp án [100]

f-d

Câu 4150856 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prim

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

cf

Đáp án [100]

fc

Đáp án [100]

c-f

Đáp án [100]

f-c

Câu 4150857 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prim

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

gc

Đáp án [100]

cg

Đáp án [100]

c-g

Đáp án [100]

g-c

Câu 4150858 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prime

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

df

Đáp án [100]

fd

Đáp án [100]

d-f

Đáp án [100]

f-d

Câu 4150859 Loại câu: Thuật toán Prim

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Prim.

Prim

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Prim là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

cf

Đáp án [100]

fc

Đáp án [100]

c-f

Đáp án [100]

f-c

Câu 4150860 Loại câu: Bài toán và thuật toán

Hãy ghép cặp thuật toán với bài toán phù hợp.
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Thuật toán Dijkstra

 Để giải bài toán tìm đường đi ngắn nhất

Thuật toán Prim

 Để giải bài toán tìm cây khung nhỏ nhất

Thuật toán Kruskal

 Để giải bài toán tìm cây khung nhỏ nhất
Câu 4150861 Loại câu: Bao nhiêu đồ thị

Có thể xây dựng được bao nhiêu đồ thị vô hướng (không nhất thiết phải liên thông) với n đỉnh?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

n(n-1)

[0]

n(n-1)/2

[0]

2n

[0]

n!

Đáp án [100]

2(n(n-1)/2

[0]

Đáp án khác

Câu 4150862 Loại câu: Tính trọng số của cây khung

Cho đồ thị vô hướng với trọng số \( G \) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \( G \).

Cây khung nhỏ nhất
Trọng số của cây khung nhỏ nhất của đồ thị \(G \) là


Đáp án [100]

169
Câu 4150863 Loại câu: Tính trọng số của cây khung

Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).

Tính trọng số của cây khung
Trọng số của cây khung nhỏ nhất của đồ thị \(G\) là


Đáp án [100]

163
Câu 4150864 Loại câu: Tính trọng số của cây khung

Cho đồ thị vô hướng với trọng số \(G\) như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).

Cây khung nhỏ nhất
Trọng số của cây khung nhỏ nhất của đồ thị \(G\) là


Đáp án [100]

143
Câu 4150865 Loại câu: Tính trọng số của cây khung

Xét đồ thị có trọng số  \(G\)như dưới đây. Hãy tính trọng số của cây khung nhỏ nhất của \(G\).

Cây khung nhỏ nhất
Trọng số của cây khung nhỏ nhất của \(G\) là

Đáp án [100]

242
Câu 4150866 Loại câu: Thuật toán Kruskal

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.

Kruskal

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

dh

Đáp án [100]

hd

Đáp án [100]

d-h

Đáp án [100]

h-d

Câu 4150867 Loại câu: Thuật toán Kruskal

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.

Kruskal

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

df

Đáp án [100]

fd

Đáp án [100]

d-f

Đáp án [100]

f-d

Câu 4150868 Loại câu: Thuật toán Kruskal

Các cạnh in đậm của đồ thị dưới đây mô tả một phần của cây khung nhỏ nhất đã được tìm thấy bởi thuật toán Kruskal.

Kruskal

 Cạnh tiếp theo của cây khung nhỏ nhất tìm được theo thuật toán Kruskal là cạnh ____________.
Chú ý: bạn chỉ điền hai đầu mút của cạnh, ví dụ cạnh \(a-b\) thì viết đơn giản là ab.


0

Đáp án [100]

bf

Đáp án [100]

fb

Đáp án [100]

f-f

Đáp án [100]

f-b

Câu 4150869 Loại câu: Tồn tại cây khung

Cho đồ thị vô hướng trọng số trên cạnh như dưới đây



 Hỏi có tồn tại cây khung nhỏ nhất mà không chứa đồng thời hai cạnh \(a-b\) và \(a-c\) hay không?


[0]

true

Có

Đáp án [100]

false

Không
Câu 4150870 Loại câu: Tồn tại cây khung

Cho đồ thị vô hướng với trọng số trên cạnh như dưới đây



 Hỏi có tồn tại cây khung nhỏ nhất chứa cạnh \(d-f\) hay không?


[0]

true

Có

Đáp án [100]

false

Không
Câu 4150871 Loại câu: Đồ thị không trọng số

Xét một đồ thị có hướng với n đỉnh và m cạnh sao cho tất cả các cạnh đều có trọng số các cạnh bằng nhau. Tìm độ phức tạp của thuật toán đã biết tốt nhất để tính cây khung nhỏ nhất của đồ thị?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

O(m+n)

[0]

O(m logn)

[0]

O(mn)

[0]

O(n logm)

[0]

Đáp án khác

Câu 4150872 Loại câu: Tính số đỉnh có bậc là x

Điền số thích hợp vào chỗ trống:

Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 14 đỉnh và 30 cạnh đều có bậc là 3 hoặc 5. 

Do đó, số đỉnh có bậc là 3 của đồ thị G  = {1:NUMERICAL:=5} 

Câu 4150874 Loại câu: Tính số đỉnh có bậc là x 2

Điền số thích hợp vào chỗ trống:

Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 15 đỉnh và 25 cạnh đều có bậc là 2 hoặc 7. 

Do đó, số đỉnh có bậc là 2 của đồ thị G  = {1:NUMERICAL:=11} 

Câu 4150876 Loại câu: Tính số đỉnh có bậc là x 3

Điền số thích hợp vào chỗ trống:

Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 54 cạnh đều có bậc là 3 hoặc 7. 

Do đó, số đỉnh có bậc là 3 của đồ thị G  = {1:NUMERICAL:=8} 

Câu 4150878 Loại câu: Tính số đỉnh có bậc là x 4

Điền số thích hợp vào chỗ trống:

Biết rằng mỗi đỉnh của đồ thị vô hướng G=(V,E) với 20 đỉnh và 52 cạnh đều có bậc là 4 hoặc 7. 

Do đó, số đỉnh có bậc là 4 của đồ thị G  = {1:NUMERICAL:=12} 

Câu 4150880 Loại câu: Số thành phần liên thông 1

Gọi G là một đồ thị đơn giản có 20 đỉnh và 8 thành phần liên thông. Nếu chúng ta xóa một đỉnh trong G, thì số thành phần trong G sẽ nằm trong khoảng nào dưới đây?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

7 - 19

[0]

8-20

[0]

8-19

[0]

7-20

[0]

Đáp án khác

Câu 4150881 Loại câu: Số lượng cạnh tối đa trong một chu trình trên đồ thị không chu trình

Số lượng cạnh đối đa trong một chu trình trên một đồ thị vô hướng không chu trình gồm n đỉnh là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

n-1

[0]

n

[0]

n+1

[0]

2n-1

[0]

Đáp án khác

Câu 4150882 Loại câu: Tìm đường đi đơn ngắn nhất trong đồ thì tổng quát

Thuật toán nào dưới đây hiệu quả nhất để tìm đường đi đơn ngắn nhất giữa 2 trong đồ thị tổng quát?

Đáp án [100] Đáp án khác


[0] Dijkstra


[0] Bellman-Ford


[0] Floyd-Warshall


[0] Prim


[0] Kruskal
Câu 4150883 Loại câu: Xác định đỉnh trong tìm đường 1

Cho đồ thị có hướng như trên hình vẽ:

dij


Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

[0]

B

[0]

C

Đáp án [100]

D

[0]

E

[0]

F

Câu 4150884 Loại câu: Xác định đỉnh trong tìm đường 2

Cho đồ thị có hướng như trên hình vẽ:

Dij

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:

[0]

E, D, F, C, B

[0]

E, D, C, B, F

[0]

E, C, B, F, D

[0]

E, C, B, D, F

Đáp án [100]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150885 Loại câu: Xác định đỉnh trong tìm đường 3

Cho đồ thị có hướng như trên hình vẽ:

Dij

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:

Đáp án [100]

E, D, B, F, C

[0]

E, D, C, B, F

[0]

E, C, B, F, D

[0]

E, C, B, D, F

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150886 Loại câu: Xác định đỉnh trong tìm đường 4

Cho đồ thị có hướng như trên hình vẽ:

Dij

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

 Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

[0]

B

[0]

C

[0]

D

[0]

E

Đáp án [100]

F

Câu 4150887 Loại câu: Xác định đỉnh trong tìm đường 5

Cho đồ thị có hướng như trên hình vẽ:

Dij

Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

Hãy xác định thứ tự lần lượt các đỉnh mà thuật toán tìm được đường đi ngắn nhất từ A đến chúng trên đồ thị đã cho:

[0]

C, E, B, D, F

[0]

C, E, F, D, B

[0]

C, F, E, D, B

[0]

C, F, E, B, D

Đáp án [100]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150888 Loại câu: Xác định đỉnh trong tìm đường 6

Cho đồ thị có hướng như trên hình vẽ:

dij

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

 Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

[0]

B

Đáp án [100]

C

[0]

D

[0]

E

[0]

F

Câu 4150889 Loại câu: Xác định đỉnh trong tìm đường 7

Cho đồ thị như trên hình vẽ:

Dij

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

 Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ đỉnh A đến nó là đỉnh nào ?

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

[0]

B

[0]

C

[0]

D

Đáp án [100]

E

[0]

F

Câu 4150890 Loại câu: Xác định đỉnh trong tìm đường 8

Cho đồ thị có hướng như trên hình vẽ:

Dij

Hãy áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại của đồ thị. Lưu ý rằng, theo cách thức hoạt động của thuật toán, thì sau mỗi bước lặp, thuật toán sẽ tìm được đường đi ngắn nhất từ đỉnh A đến một đỉnh còn lại của đồ thị.

 Hỏi rằng đỉnh thứ tư mà thuật toán tìm được đường đi ngắn nhất từ A đến nó là đỉnh nào ?

Chú ý: khi thực hiện thuật toán, luôn duyệt đỉnh theo thứ tự từ điển: A, B, C, D, E, F

Đáp án [100]

B

[0]

C

[0]

D

[0]

E

[0]

F

Câu 4150891 Loại câu: Cấu trúc nào phù hợp

Để cài đặt thuật toán đường đi ngắn nhất Dijkstra trên đồ thị không có trọng số để nó chạy trong thời gian tuyến tính, cấu trúc dữ liệu sẽ được sử dụng là:
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

Đáp án [100]

Hàng đợi

[0]

Ngăn xếp

[0]

Đống (Heap)

[0]

B-Tree

Câu 4150892 Loại câu: Cấu trúc Low, Num 1

Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4, 6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10), (8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:

Hỏi giá trị của Low[6] bằng bao nhiêu?

Đáp án [100] 4


[0] 5


[0] 6


[0] 1


[0] 3


[0] Đáp án khác
Câu 4150893 Loại câu: Cấu trúc Low, Num 2

Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4, 6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10), (8,11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:

Hỏi giá trị của Low[11] bằng bao nhiêu?

[0] 4


[0] 5


Đáp án [100] 6


[0] 1


[0] 3


[0] Đáp án khác
Câu 4150894 Loại câu: Cấu trúc Low, Num 3

Cho đồ thị vô hướng G = (V, E), với V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} và E = {(1, 2), (1, 3), (2, 3), (3, 4), (4, 6), (4, 9), (5, 6), (5, 8), (5, 11), (6, 7), (6, 9), (7, 9), (7, 10), (8,11), (10, 11)}. Thực hiện phân tích cây tìm kiếm theo chiều sâu trên đồ thị G với lời gọi hàm AnalyzeDFS(1, -1), với hàm AnalyzeDFS mô tả phía dưới:

Hỏi giá trị của Low[10] bằng bao nhiêu?

Đáp án [100] 4


[0] 5


[0] 6


[0] 1


[0] 3


[0] Đáp án khác
Câu 4150895 Loại câu: DFS 1

Hãy xác định đâu là cây tìm kiếm theo chiều sâu xuất phát từ đỉnh 1 (kí hiệu là DFS(1)) trên đồ thị sau:

dfs1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Đáp án [100]

1

[0]

2

[0]

3

[0]

4

[0]

5

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150896 Loại câu: DFS 2

Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 3 (kí hiệu là DFS(3)) trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Đáp án [100]

1

[0]

2

[0]

3

[0]

4

[0]

5

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150897 Loại câu: DFS 3

Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 2 (kí hiệu là DFS(2)) trên đồ thị sau:

dfs1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1, 2 ,3, 4, 5, 6, 7, 8.

[0]

1

Đáp án [100]

2
Loại: -25

3

[0]

3

[0]

4

[0]

1

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150898 Loại câu: DFS 4

Hãy xác định đâu là cây theo chiều sâu xuất phát từ đỉnh 4 (kí hiệu là DFS(4)) trên đồ thị sau:

DFS(4)

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Đáp án [100]

1

[0]

2

[0]

3

[0]

4

[0]

5

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150899 Loại câu: DFS Path 1

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 4 trên đồ thị sau:

DFS(4)

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 4 đến đỉnh 7 là:

Đáp án [100]

4 --> 2 --> 5 --> 7

[0]

4 --> 5 --> 7

[0]

4 --> 2 --> 6 --> 7

[0]

4 --> 2 --> 8 --> 6 --> 7

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150900 Loại câu: DFS Path 2

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:

[0]

1 --> 4 --> 5 --> 7 --> 6

[0]

1 --> 2 --> 6

[0]

1 --> 2 --> 8 --> 6

[0]

1 --> 2 --> 5 --> 7 --> 6

Đáp án [100]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

[0]

1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6

Câu 4150901 Loại câu: DFS Path 3

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 1 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 1 đến đỉnh 6 trên cây DFS là:

Đáp án [100]

1 --> 2 --> 4 --> 5 --> 7 -->6

[0]

1 --> 2 --> 6

[0]

1 --> 2 --> 8 --> 6

[0]

1 --> 2 --> 5 --> 7 --> 6

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

[0]

1 --> 3 --> 4 --> 2 -->5 --> 7 --> 6

Câu 4150902 Loại câu: DFS Path 4

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:

[0]

3 -->  4 --> 5 --> 7 -->6

[0]

3 --> 1 --> 2 --> 6

[0]

3 --> 4 --> 2  --> 6

[0]

3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6

Đáp án [100]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng
Loại: -25

3 --> 4 --> 2 -->8 --> 6

Câu 4150903 Loại câu: DFS Path 5

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:

Đáp án [100]

2 --> 1  --> 4  --> 5 --> 7

[0]

2 --> 8 --> 6 --> 7

[0]

2 --> 5  --> 7

[0]

2  --> 1 --> 8 --> 6 --> 7

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150904 Loại câu: DFS Path 6

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 3 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 3 đến đỉnh 6 trên cây DFS là:

Đáp án [100]

3 --> 1 --> 2 --> 4 --> 5 --> 7 -->6

[0]

3 --> 1 --> 2 --> 6

[0]

3 --> 4 --> 2  --> 6

[0]

3 --> 1 --> 4 --> 2 --> 5 --> 7 --> 6

[0]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

[0]

3 --> 4 --> 2 -->8 --> 6

Câu 4150905 Loại câu: DFS Path 7

Áp dụng thuật toán tìm kiếm theo chiều sâu DFS xuất phát từ đỉnh 2 trên đồ thị sau:

1

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển: 1,2 ,3, 4, 5, 6, 7, 8.

Kết thúc thuật toán, ta có đường đi từ đỉnh 2 đến đỉnh 7 là:

[0]

2 --> 4  --> 5 --> 7

[0]

2 --> 8 --> 6 --> 7

[0]

2 --> 5  --> 7

[0]

2  --> 1 --> 8 --> 6 --> 7

Đáp án [100]

Trong các lựa chọn đưa ra, không có lựa chọn nào đúng

Câu 4150906 Loại câu: Đường đi 1

Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 4 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?

Đáp án [100]

1 --> 6 --> 4

[0]

1 --> 2 --> 5 --> 4

[0]

1 --> 2 -->6 --> 4

[0]

1 --> 3--> 2 --> 5 --> 4

[0]

1 --> 5 --> 4

[0] Đáp án khác
Câu 4150907 Loại câu: Đường đi 2

Cho đồ thị vô hướng G=(V,E), trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6, 7} và tập cạnh E ={(1,2), (1,3), (2,4), (2,5), (3,5), (4,6), (4,7), (5, 6), (5, 7), (6, 7)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 1 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh 1 đến đỉnh 6 trong phép duyệt theo chiều rộng là đường đi nào dưới đây?

Đáp án [100]

1 --> 2 --> 4 --> 6

[0]

1 --> 3 --> 5 --> 7 --> 6

[0]

1 --> 2 -->5 --> 6

[0]

1 --> 3--> 5 --> 6

[0]

1 --> 5 --> 7 --> 6

[0] Đáp án khác
Câu 4150908 Loại câu: Đường đi 3

Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {a, b, c, d, e, f, g} và tập cạnh E ={(a,b), (a,c), (b,d), (b,e), (c,e), (d,f), (d,g), (e, f), (e, g), (f, g)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phải từ đỉnh a (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi đường đi từ đỉnh a đến đỉnh f trong phép duyệt theo chiều rộng là đường đi nào dưới đây?

Đáp án [100]

a --> b --> d --> f

[0]

a --> c --> e --> g --> f

[0]

a --> b -->e --> f

[0]

a --> c--> e --> f

[0]

a --> e --> g --> f

[0] Đáp án khác
Câu 4150909 Loại câu: Đường đi 1

Cho đồ thị vô hướng G=(V,E) trong đó tập đỉnh V = {1, 2, 3, 4, 5, 6} và tập cạnh E ={(1,2), (1,3), (1,6),(2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Thực hiện phép duyệt đồ thị G theo chiều rộng xuất phát từ đỉnh 6 (khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển). Hỏi độ dài đường đi (tính theo số lượng cạnh) từ đỉnh 6 đến đỉnh 3 là bao nhiêu?

Đáp án [100]

2

[0]

1

[0]

3

[0]

4

[0]

5

[0] Đáp án khác
Câu 4150910 Loại câu: MultiChoice_vohuong 1

Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh s (kí hiệu: BFS(s)) trên đồ thị sau:

BFS

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.

Đáp án [100]

BFS1

[0]

BFS2

[0]

BFS3

[0]

BFS4

[0] Đáp án khác
Câu 4150911 Loại câu: MultiChoice_vohuong 2

Hãy xác định đâu là cây tìm kiếm theo chiều rộng xuất phát từ đỉnh b (kí hiệu: BFS(b)) trên đồ thị sau:

BFS

Chú ý: khi duyệt các đỉnh thì bắt buộc xét theo thứ tự từ điển.

Đáp án [100]

BFS

[0]

BFS

[0]

BFS

[0]

BFS4

[0] Đáp án khác
Câu 4150912 Loại câu: Tìm thành phần liên thông

Chúng ta có thể sử dụng các phương pháp tìm kiếm nào dưới đây để tìm tất cả các thành phần liên thông trong đồ thị vô hướng có trọng số G = (V,E, c)?

[0] Tìm kiếm theo chiều rộng (BFS)


[0] Tìm kiếm theo chiều sâu (DFS)


Đáp án [100] Tìm kiếm theo chiều rộng và chiều sâu


[0] Đáp án khác
Câu 4150913 Loại câu: Tìm thành phần liên thông mạnh

Thuật toán nào dưới đây là phù hợp nhất để tìm thành phần liên thông mạnh trong một đồ thị có trọng số?

[0] Thuật toán tìm kiếm theo chiều rộng


Đáp án [100] Thuật toán tìm kiếm theo chiều sâu


[0] Thuật toán tìm kiếm theo chiều rộng và chiều sâu


[0] Đáp án khác


[0] Thuật toán dijkstra
Câu 4150914 Loại câu: Ứng dụng tìm đường đi ngắn nhất trong đồ thị không trọng số

Tìm đường đi ngắn nhất giữa 2 đỉnh trong đồ thị có hướng không trọng số G = (V, E) thì dùng thuật toán nào dưới đây phù hợp nhất? 

Chú ý đường đi ngắn nhất giữa 2 đỉnh là đường đi qua ít cạnh nhất.

Đáp án [100] Tìm kiếm theo chiều rộng


[0] Tìm kiếm theo chiều sâu


[0] Thuật toán dijkstra


[0] Thuật toán Bellman-Ford


[0] Đáp án khác
Câu 4150915 Loại câu: Độ phức tạp duyệt tìm thành phần liên thông

Thuật toán hiệu quả nhất để tìm số lượng các thành phần liên thông trong một đồ thị vô hướng trên n đỉnh và m cạnh có độ phức tạp về thời gian là bao nhiêu?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

  θ(n)

[0]

θ(m)

Đáp án [100]

θ(m + n) 

[0]

θ(mn)

[0]

Đáp án khác

Câu 4150916 Loại câu: Cấu trúc dữ liệu phù hợp để duyệt

Cấu trúc dữ liệu nào dưới đây phù hợp với duyệt độ thị theo chiều rộng?
Your answer is correct. Your answer is partially correct. Your answer is incorrect.

[0]

Ngăn xếp

Đáp án [100]

Hàng đợi

[0]

Danh sách liên kết

[0]

Đáp án khác
{% endblock %}